/*
Copyright (c) 2025 HeZongLun
NahidaProject is licensed under Mulan PSL v2.
You can use this software according to the terms and conditions of the Mulan
PSL v2.
You may obtain a copy of Mulan PSL v2 at:
         http://license.coscl.org.cn/MulanPSL2
THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS, WITHOUT WARRANTIES OF ANY
KIND, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO
NON-INFRINGEMENT, MERCHANTABILITY OR FIT FOR A PARTICULAR PURPOSE.
See the Mulan PSL v2 for more details.
*/

#include <iostream>
#include <bitset>
#include <string>
#include <cmath>

namespace NahidaProject {

	struct __declspec(dllexport) BKDRHash {
		size_t operator()(const std::string& s) {
			size_t value = 0;
			for (auto ch : s) {
				value = value * 131 + ch;
			}
			return value;
		}
	};

	struct __declspec(dllexport) APHash {
		size_t operator()(const std::string& s) {
			size_t value = 0;
			for (size_t i = 0; i < s.size(); i++) {
				if ((i & 1) == 0) {
					value ^= ((value << 7) ^ s[i] ^ (value >> 3));
				}
				else {
					value ^= (~((value << 11) ^ s[i] ^ (value >> 5)));
				}
			}
			return value;
		}
	};

	struct __declspec(dllexport) DJBHash {
		size_t operator()(const std::string& s) {
			if (s.empty()) return 0;
			size_t value = 5381;
			for (auto ch : s) {
				value += (value << 5) + ch;
			}
			return value;
		}
	};

	template<size_t N, class K = std::string, class Hash1 = BKDRHash, class Hash2 = APHash, class Hash3 = DJBHash>
	class __declspec(dllexport) BloomFilter {
	public:
		void Set(const K& key) {
			size_t i1 = Hash1()(key) % N;
			size_t i2 = Hash2()(key) % N;
			size_t i3 = Hash3()(key) % N;

			_bs.set(i1);
			_bs.set(i2);
			_bs.set(i3);
		}

		bool Test(const K& key) const {
			size_t i1 = Hash1()(key) % N;
			if (!_bs.test(i1)) return false;

			size_t i2 = Hash2()(key) % N;
			if (!_bs.test(i2)) return false;

			size_t i3 = Hash3()(key) % N;
			return _bs.test(i3);
		}

		void Clear() {
			_bs.reset();
		}

		size_t GetUsedBits() const {
			return _bs.count();
		}

		double EstimateFalsePositiveRate(size_t element_count) const {
			if (element_count == 0) return 0.0;

			const double m = N;
			const double k = 3.0;
			const double n = element_count;

			const double exponent = -k * n / m;
			return pow(1 - std::exp(exponent), k);
		}

		size_t EstimateElementCount() const {
			const size_t used = GetUsedBits();
			if (used == 0) return 0;

			const double m = N;
			const double k = 3.0;
			const double X = used;

			return static_cast<size_t>(-m / (k)*std::log(1 - X / m));
		}

		constexpr size_t Capacity() const noexcept {
			return N;
		}

		double LoadFactor() const {
			return static_cast<double>(GetUsedBits()) / N;
		}

	private:
		std::bitset<N> _bs;
	};
}
